1311E - Construct the Binary Tree - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int t, n, d, a[MAXN], cnt[MAXN], clv, ans[MAXN];
int main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	cin >> t;
	while (t--) {
		cin >> n >> d;
		d = -d;
		for (int i = 0;i < n;i++) {
			cnt[i] = 1;
			d += i;
		} 
		if (d < 0) {
			cout << "NO" << endl;
			continue;
		}
		clv = 1;
		for (int i = n - 1;i >= 1;i--) {
			if (d == 0) break;
			else if (d <= i - clv) {
				cnt[i - d]++;
				cnt[i]--;
//				cout << "Moving level " << i << " to level " << i - d << endl;
				d = 0; 
//				cout << "Got " << d << " more depth sum" << endl;
				break;
			}
			else {
				if (clv >= i) break;
				cnt[clv]++;
				cnt[i] = 0;
				d -= i - clv;
//				cout << "Moving level " << i << " to level " << clv << endl; 
//				cout << "Got " << d << " more depth sum" << endl;
				if (cnt[clv] >= (1 << clv)) clv++;
			}
		}
		if (d > 0) {
			cout << "NO" << endl;
			continue;
		}
		cout << "YES" << endl;
		int lst = 1, cnt2 = 1;
		for (int i = 1;i < n;i++) {
			for (int j = 1;j <= cnt[i];j++) {
				ans[++cnt2] = lst;
				if (j % 2 == 0) lst--;
			}
			lst = cnt2;
		}
		for (int i = 2;i <= n;i++) {
			cout << ans[i] << " ";
		}
		cout << endl;
		for (int i = 1;i <= n;i++) cnt[i] = 0;
	}
	return 0;
}